package main

/*
由于我们只关心每个字母出现次数的奇偶性，因此可以将「字母出现次数」转换成「字母出现次数的奇偶性」，这可以用一个长为 $10$ 的二进制串表示，二进制串的第 $i$ 位为 $0$ 表示第 $i$ 个小写字母出现了偶数次，为 $1$ 表示第 $i$ 个小写字母出现了奇数次。

考虑字母出现次数的前缀和，由于只考虑奇偶性，我们也可以将其视作一个长为 $10$ 的二进制串。若有两个不同下标的前缀和相同，则说明这两个下标之间的子串的所有字母均出现偶数次，符合题目要求。

因此，我们可以在求前缀和的同时，用一个长为 $2^{10}=1024$ 的 $cnt$ 数组统计每个前缀和二进制串出现的次数，从而得到相同前缀和的对数。

对于「至多一个字母出现奇数次」，我们可以翻转当前前缀和的每个比特，然后去 $cnt$ 中查找该前缀和的出现次数。

将所有统计到的次数累加即为答案。

这一技巧在前缀和的题目中经常用到，例如[「560. 和为K的子数组」](https://leetcode-cn.com/problems/subarray-sum-equals-k/)。

*/

// github.com/EndlessCheng/codeforces-go
func wonderfulSubstrings(word string) int64 {
	cnt := [1024]int{1} // 空串对应的二进制串为 0，其出现次数为 1
	ans, pre := 0, 0
	for _, b := range word {
		pre ^= 1 << (b - 'a') // 计算当前前缀和
		ans += cnt[pre] // 所有字母均出现偶数次
		for i := 1; i < 1024; i <<= 1 { // 枚举其中一个字母出现奇数次
			ans += cnt[pre^i] // 翻转第 i 个字母的出现次数的奇偶性
		}
		cnt[pre]++
	}
	return int64(ans)
}
